package com.example.algorithm.manacher;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 *
 *  示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 *
 *  示例 2：
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 *  示例 3：
 * 输入：s = "a"
 * 输出："a"
 *
 *  提示：
 *  1 <= s.length <= 1000
 *  s 仅由数字和英文字母（大写和/或小写）组成
 */
public class Leetcode5_LongestPalindrome {
    public static void main(String[] args) {
        String s = "aaaa";
        System.out.println(new Solution().longestPalindrome(s));

    }

    static class Solution {

        /**
         * Manacher算法
         * 1. 转成字符数组，添加特定字符
         * 2. 遍历新数组，记录每个位置i的最长回文半径results[i]
         *   2.1 选定当前中心位置center及右边界right，以中心位置计算i的镜像位置i_mirror
         *   2.2 如果i不超过右边界， results[i] 取right – i 与results[i_mirror] 的较小值
         *   2.3 以i为中心， results[i]为半径再扩展比对，并更新results[i]
         *   2.4 如果i+result[i] 超过右边界，则更新center 和right (拉车)
         * 3. 遍历results[i]找到最大的回文半径
         * 4. 换算成原始字符串中起始位置及长度，返回最长回文子串
         * @param s
         * @return
         */
        private String longestPalindrome4(String s) {
            if (s.length() <= 1) return s;
            char[] chars = s.toCharArray();
            int start = 0, maxLen = 1; // start表示最长回文子串的开始,maxLen表示最长回文子串的长度
            char[] newChars = preProcess(chars);

            int n = newChars.length;
            int[] results = new int[n];//以该索引位置为中心的最长回文长度
            int center = 0; int right = 0;//中心及右边范围,初始为0
            for (int i = 1; i < n - 1; i++) { //计算每个位置最长回文长度
                int iMirror = 2 * center - i;//镜像位置
                if (i < right){
                    results[i] = Math.min(right - i, results[iMirror]);
                } else {
                    results[i] = 0;//等于right 的情况
                }
                // 利用中心扩展法,以i为中心左右扩展继续比对
                while (newChars[i + 1 + results[i]] == newChars[i - 1 - results[i]])
                    results[i]++;

                if(i + results[i] > right){ //更新center及right
                    center=i;
                    right = i + results[i];
                }
            }
            int centerIndex = 0;

            for (int i = 1; i < n - 1; i++) {// 遍历result找出sresults中的最大值(最长回文子串的长度)
                if (results[i] > maxLen) {
                    maxLen = results[i];
                    centerIndex = i;
                }
            }
            start = (centerIndex - maxLen) / 2; // 换算成原字符串下标

            return new String(chars, start, maxLen);
        }

        /**
         * 解法三:中心扩散法
         * 遍历每个字符，以其为中心同时向两边扩散(奇偶两种)
         * 得到扩散的最大的子串
         * @param s
         * @return
         */
        private String longestPalindrome3(String s) {
            if (s.length() <= 1) return s;
            int szie = s.length();
            char[] chars = s.toCharArray();
            int start = 0, maxLen = 1; // start表示最长回文子串的开始,maxLen表示最长回文子串的长度
            for (int i = 0; i < szie; i++) {
                int oddMaxLen = expandAroundCenter(chars, i, i);// 奇数长度以i为中心扩散
                int evenMaxLen = expandAroundCenter(chars, i, i + 1); // 偶数长度以i为中心扩散
                int len = Math.max(evenMaxLen, oddMaxLen);

                if (len > maxLen) {
                    start = i - (len - 1) / 2;
                    maxLen = len;
                }
            }
            return new String(chars, start, maxLen);
        }


        /**
         * 解法二:动态规划
         * 观察暴力法,发现有很多重复的计算可以使用动态规划规避重复计算
         * 1.原问题与子问题:
         *   判断字符串是否是回文串可以先判断头尾是否相同然后去掉头尾判断还是否是回文串
         *
         * 2.设计状态:
         *   f(i,j)表示以i开头以j结尾的字符串是否是回文串
         *
         * 3.状态转移方程
         *   f(i,j) = chars[i]== chars[j] && f(i+1, j-1) 其中 j-i >= 2
         *   f(i,i+1) = chars[i]== chars[j]
         *
         *
         * 4.边界值
         * @param s
         * @return
         */
        private String longestPalindrome2(String s) {
            int len = s.length();
            if (len <= 1) return s;
            char[] chars = s.toCharArray();
            int start = 0, maxLen = 1; // start表示最长回文子串的开始,maxLen表示最长回文子串的长度
            boolean[][] dp = new boolean[len][len];// dp[i][j]表示以i开头以j结尾的字符串是否是回文串
            // 首先初始化子串长度为1的状态
            for (int i = 0; i < len; i++) {
                dp[i][i] = true;
            }

            // 子串长度依次增加
            for (int subLen = 2; subLen <= len; subLen++) { // 子串长度依次2 ~ n
                for (int left = 0; left + subLen - 1 < len; left++) {
                    int right = left + subLen - 1;
                    // 判断子串是否是回文串
                    if (subLen == 2) {
                        dp[left][right] = (chars[left] == chars[right]);
                    } else {
                        dp[left][right] = (chars[left] == chars[right]) && dp[left + 1][right - 1];
                    }

                    // 更新最大长度
                    if (subLen > maxLen && dp[left][right]) {
                        start = left;
                        maxLen = subLen;
                    }
                }
            }

            return new String(chars, start, maxLen);
        }

        /**
         * 暴力法
         * @param s
         * @return
         */
        private String longestPalindrome1(String s) {
            if (s.length() <= 1) return s;
            char[] chars = s.toCharArray();
            int start = 0, maxLen = 1; // start表示最长回文子串的开始,maxLen表示最长回文子串的长度
            for (int i = 0; i < chars.length; i++) {
                for (int j = i + 1; j < chars.length; j++) {
                    if((j - i + 1) > maxLen && isPalindrome(chars, i, j)) { // 判断子串left~rights否是回文串
                        start = i;
                        maxLen = j - i + 1;
                    }
                }
            }
            return new String(chars, start, maxLen);
        }

        // 预处理将所给字符串变换为用于Manacher算法的字符串
        private char[] preProcess(char[] chars) {
            char[] newChars = new char[chars.length * 2 + 3];
            newChars[0] = '^';
            int index = 1;
            for (int i = 0; i < chars.length; i++) {
                newChars[index++] = '#';
                newChars[index++] = chars[i];
            }

            newChars[index++] = '#';
            newChars[index++] = '$';
            return newChars;
        }

        // 得到以left,right为中心的最大回文串长度(left == right 奇, right == left + 1 偶)
        private int expandAroundCenter(char[] chars, int left, int right) {
            while (left >= 0 && right < chars.length && chars[left] == chars[right]) {
                --left;
                ++right;
            }
            return right - left - 2 + 1;
        }

        // 判断left~right的子串是否是回文串
        private boolean isPalindrome(char[] chars, int left, int right) {
            while (left <= right) {
                if (chars[left++] != chars[right--]) return false;
            }
            return true;
        }

        public String longestPalindrome(String s) {
            return longestPalindrome4(s);
        }
    }
}
